package leetcode.editor.cn.dsa14_greedyAlgorithm;
// 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
// 对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i
//]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。 
// 
// 示例 1:
// 输入: g = [1,2,3], s = [1,1]
// 输出: 1
// 解释:
// 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
// 虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
// 所以你应该输出1。
//
// 示例 2: 
// 输入: g = [1,2], s = [1,2,3]
// 输出: 2
// 解释:
// 你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
// 你拥有的饼干数量和尺寸都足以让所有孩子满足。
// 所以你应该输出2.
//
// 提示： 
// 1 <= g.length <= 3 * 104
// 0 <= s.length <= 3 * 104 
// 1 <= g[i], s[j] <= 231 - 1 
// 
// Related Topics 贪心算法 
// 👍 228 👎 0

public class AssignCookies455 {
    public static void main(String[] args) {
        Solution solution = new AssignCookies455().new Solution();
        int[] g = {2,1,3}, s = {1,1};
        System.out.println(solution.findContentChildren(g, s)); //1
        int[] g2 = {2,1}, s2 = {1,3,2};
        System.out.println(solution.findContentChildren(g2, s2)); //2
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findContentChildren(int[] g, int[] s) {
            int m = g.length, n = s.length;
            if (n == 0) return 0;
            // 对两个数组进行排序
            quickSort(g, 0, m - 1);
            quickSort(s, 0, n - 1);
            /**
             * 饼干尺寸s：[2,4,6,8]
             * 孩子胃口g：[1,3,5,7,9]
             * 倒序遍历所有的饼干，依次找出每个饼干能满足的最大孩子胃口，然后次数累加
             * 如果某个饼干不能满足孩子，那么当前的次数就是最优解，后面的饼干也肯定不满足
             * 注意查找孩子胃口时应该从上一次能满足的位置-1开始倒序查找
             */
            int count = 0, end = m;
            for (int i = n - 1; i >= 0; i--) {
                // 记录上一次能满足的最大位置
                end = checkCanSatisfy(s[i], g, end);
                if (end == -1) break; // 某个饼干不能满足，直接终止
                count++;
            }
            return count;
        }

        /**
         * 查找当前饼干尺寸是否能满足某个孩子的胃口
         * @param x 当前饼干尺寸
         * @param g 孩子集合
         * @param end 查找终止位置
         * @return 能满足则返回孩子下标，否则返回-1
         */
        public int checkCanSatisfy(int x, int[] g, int end) {
            for (int i = end - 1; i >= 0; i--) {
                if (g[i] <= x) return i;
            }
            return -1;
        }

        // 快速排序
        public void quickSort(int[] arr, int low, int high) {
            int i = low, j = high;
            int temp = arr[low];
            while (i < j) {
                while (i < j && arr[j] >= temp) j--;
                if (i < j) arr[i++] = arr[j];
                while (i < j && arr[i] <= temp) i++;
                if (i < j) arr[j--] = arr[i];
            }
            arr[i] = temp;
            if (low < i - 1) quickSort(arr, low, i - 1);
            if (high > i + 1) quickSort(arr, i + 1, high);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}